package org.example.algorithm.dp;

import java.util.Arrays;

//122. 买卖股票的最佳时机 II
public class MaxProfit2Solution {
    //贪心算法
    public int maxProfit(int[] prices) {
        int sum = 0;
        for (int i=1;i<prices.length;i++) {
            if (prices[i] > prices[i-1]) {
                sum += prices[i] - prices[i-1];
            }
        }
        return sum;
    }

    //dp
    //dp[i][0]代表第i天不持有任何股票的收益，dp[i][1]代表第i天持有股票的收益
    public int maxProfit2(int[] prices) {
        int len = prices.length;
        int[][] dp = new int[len][2];
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        for (int i=1;i<len;i++) {
            dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]);
            dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] - prices[i]);
        }
        return dp[len-1][0];
    }

    //dp优化内存占用
    public int maxProfit3(int[] prices) {
        int len = prices.length;
        int dp0 = 0;
        int dp1 = -prices[0];
        for (int i=1;i<len;i++) {
            int temp = dp0;
            dp0 = Math.max(dp0,  dp1 + prices[i]);
            dp1 = Math.max(dp1, temp - prices[i]);
        }
        return dp0;
    }

    //dfs+mem
    public int maxProfit4(int[] prices) {
        int len = prices.length;
        int[][] mem = new int[len][2];
        for (int i=0;i<len;i++) {
            Arrays.fill(mem[i], -1);
        }
        return dfs(prices, mem, len-1, 0);
    }

    private int dfs(int[] prices, int[][] mem, int i, int hold) {
        if (i < 0) {
            return hold == 0 ? 0 : Integer.MIN_VALUE;
        }
        if (mem[i][hold] != -1) {
            return mem[i][hold];
        }
        if (hold == 1) {
            return mem[i][hold] = Math.max(dfs(prices, mem, i-1, hold), dfs(prices, mem, i-1, 0) - prices[i]);
        }
        return mem[i][hold] = Math.max(dfs(prices, mem, i-1, hold), dfs(prices, mem, i-1, 1) + prices[i]);
    }
}
